// 题目描述
// 小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。
// 小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。
// 小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。

// 输入描述
// 第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。 
// 接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。

// 输出描述
// 输出一个整数，代表小明从起点到终点所花费的最小时间。当从起始车站不能到达终点车站时，则输出 -1。

// 输入示例
// 7 9
// 1 2 1
// 1 3 4
// 2 3 2
// 2 4 5
// 3 4 2
// 4 5 3
// 2 6 4
// 5 7 4
// 6 7 9
// 输出示例
// 12



const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// dijkstra算法，计算开始节点到各节点的最小路径和，可以不用所有节点。minDist数组的值依赖前面计算过的，路径的权值不可为负
// 时间复杂度为O(n^2),因为两个for循环，循环的是所有的节点
// 空间复杂度：O(n^2)
// prim算法和kruskal算法，计算最小树，即必须所有节点都要统计。minDist数组的值不依赖前面计算，所以路径的权值可以为负
void async function () {
    line = await readline();
    let [n, m] = line.split(' ').map(Number),
        // 当前节点距离根节点的最小路径和
        minDist = new Array(n + 1).fill(50000),
        visited = new Array(n + 1).fill(false),
        graph = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(50000)),
        // 当前节点最小路径和的入节点
        parent = new Array(n + 1).fill(0);

    // 后续节点需要求和，所以开始结点的最小路径和的值初始化为0
    minDist[1] = 0;
    while (line = await readline()) {
        let [left, right, val] = line.split(' ').map(Number);
        graph[left][right] = val
    }

    for (let i = 1; i <= n; i++) {
        // 同prim算法，计算未被访问过（未生成树）的最小路径和-类似贪心算法,局部最优达到全局最优
        let cur = null,
            minPathSum = Infinity;

        for (let j = 1; j <= n; j++) {
            if (visited[j] === false && minDist[j] < minPathSum) {
                minPathSum = minDist[j]
                cur = j
            }
        }

        // 置为访问过
        visited[cur] = true

        // 若当前节点距离源节点的路径和加上距离下一个未访问过的节点的路径,小于下一个节点距离源节点的路径和,重置
        for (let j = 1; j <= n; j++) {
            if (visited[j] === false && minDist[cur] + graph[cur][j] < minDist[j]) {
                minDist[j] = minDist[cur] + graph[cur][j]
                // 更新到达当前节点的最小路径和的父节点
                parent[j] = cur
            }
        }
    }

    console.log(minDist[n] === 50000 ? -1 : minDist[n])
}()